#include <cstdio>
#include <cstdlib>
#include <cstring>

// 乘客节点
typedef struct _PassengerNode {
  char name[20];   // 姓名
  int ticketCount; // 订票数
  char ID[20];     // 身份证
  char day[20];    // 星期几
  int seat_level;  // 舱等级
  struct _PassengerNode *next;
} PassengerNode, *PassengerList;

// 候补队列的节点
typedef struct _WaitlistNode {
  char name[20];               // 姓名
  char ID[20];                 // 身份证
  int required_sticket_number; // 预定数量
  struct _WaitlistNode *next;
} WaitlistNode, *Waitlist;

// 候补队列
typedef struct _WaitQueue {
  Waitlist front; // 头指针
  Waitlist rear;  // 尾指针
} WaitlistQueue;

// 乘客信息结构体,用于候补客户出队时把关键字返回
typedef struct _PassengerInfo {
  char name[20]; // 姓名
  char ID[20];   // 身份证
  char day[20];  // 星期几
  int num;       // 订票量
} PassengerInfo;

// 航班节点
typedef struct _Flight {
  char departure[20];             // 起点站名
  char destination[20];           // 终点站名
  char flight_id[20];             // 航班编号
  char plane_id[20];              // 飞机号
  char day[20];                   // 飞行日期(星期几)
  int capacity;                   // 总票数
  int remaining_ticket_quantity;  // 总余票量
  int remaining_ticket_quantity1; // 等级1剩余量
  int remaining_ticket_quantity2; // 等级2剩余量
  struct _Flight *next;           // next指针域
  PassengerList passenger_list; // 乘员名单域，指向乘员名单链表的头指针
  WaitlistQueue waitlist_1; // 等级1候补，等候替补的客户名单域，指向一个队列
  WaitlistQueue waitlist_2; // 等级2候补，等候替补的客户名单域，指向一个队列
} Flight, FlightNode, *FlightList;

// 初始化航班链表
void init_flights();

// 输入编号返回对应信息
Flight *search_flight_by_id();

// 初始化队列
int init_waitlist_quene(WaitlistQueue &q);

// 初始化订票乘客链表
int init_passenger_list(PassengerList &cusLinkList);

// 将订票成功的乘客节点加入到已订票链表
PassengerList add_passenger(PassengerList &head, int need, char name[],
                            char id[], char day[], int grade);

// 输出已经订票的函数
void print_passenger_info();

// 订票函数
void book_ticket();

// 订票界面
void book_ticket_interface();

// 输出对应节点信息
void print_flight_info(Flight *p);

// 将等待的客户入队
WaitlistQueue enqueue_waitlist(WaitlistQueue &q, char name[], int need,
                               char id[]);

PassengerInfo dequeue_waitlist1(FlightList &f);
PassengerInfo dequeue_waitlist2(FlightList &f);
// 由起点终点搜索航班
void search_flight_by_points();

// 搜索界面
void search_interface();

// 退票
void cancel_ticket();

// 退票界面
void cancel_ticket_interface();

// 打印全部航班信息
void list_flights(Flight *pflight);

// 菜单界面函数
int show_menu();

// 增加航班
int add_flight();

// 删除航班
int delete_flight();

// 插入和删除界面
void add_delete_flight_interface();

// 将航班信息插入到链表中
int init_add_flight(FlightList flight1);

// 对比插入航班标号，防止标号重复
int compare_flight_id(Flight *flight, char flightCodeID[]);

// 全局节点变量 航班链表
Flight *pFlight;

// 初始输入的航班信息
Flight InitialFlight[16] = {
    {"上海", "北京", "1", "A1111", "星期一", 200, 200, 90},
    {"北京", "武汉", "2", "B8942", "星期三", 200, 200, 100},
    {"武汉", "广州", "3", "C5465", "星期六", 200, 200, 100},
    {"广州", "福州", "4", "D5645", "星期五", 200, 200, 100},
    {"福州", "长沙", "5", "E4986", "星期一", 200, 200, 100},
    {"长沙", "杭州", "6", "F6545", "星期四", 200, 200, 100},
    {"杭州", "郑州", "7", "G3993", "星期二", 200, 200, 100},
    {"郑州", "南京", "8", "H6533", "星期一", 200, 200, 100},
    {"南京", "西安", "9", "I9662", "星期五", 200, 200, 100},
    {"西安", "重庆", "10", "J8526", "星期日", 200, 200, 100},
    {"重庆", "成都", "11", "K6863", "星期二", 200, 200, 100},
    {"成都", "昆明", "12", "L6666", "星期天", 150, 80, 80},
    {"昆明", "贵阳", "13", "M6546", "星期三", 100, 100, 40},
    {"贵阳", "厦门", "14", "N6562", "星期六", 200, 200, 100},
    {"厦门", "南宁", "15", "K9896", "星期三", 200, 200, 100},
    {"南宁", "北京", "16", "B8665", "星期一", 200, 100, 100},
};

// 初始化航班链表
void init_flights() {
  pFlight = (Flight *)malloc(sizeof(Flight));
  if (pFlight == NULL)
    exit(0);
  pFlight->next = NULL;
}

// 将已有航班信息插入链表
int init_add_flight(FlightList flight1) {
  Flight *p = pFlight, *q;
  for (int i = 0; i < 16; i++) {
    q = (Flight *)malloc(sizeof(Flight));
    if (q == NULL)
      return 0;

    // 利用链表把每个信息录入
    strcpy(q->departure, flight1[i].departure);
    strcpy(q->destination, flight1[i].destination);
    strcpy(q->flight_id, flight1[i].flight_id);
    strcpy(q->plane_id, flight1[i].plane_id);
    strcpy(q->day, flight1[i].day);
    q->capacity = flight1[i].capacity;
    q->remaining_ticket_quantity = flight1[i].capacity;
    q->remaining_ticket_quantity1 = flight1[i].remaining_ticket_quantity1;
    q->remaining_ticket_quantity2 =
        flight1[i].capacity - flight1[i].remaining_ticket_quantity1;

    // 初始化已订票乘客链表
    init_passenger_list(q->passenger_list);

    // 初始化等候队列
    init_waitlist_quene(q->waitlist_1);
    init_waitlist_quene(q->waitlist_2);
    q->next = p->next;
    p->next = q;
  }
  return 1;
}

// 初始化已订票乘客指针链表
int init_passenger_list(PassengerList &cusLinkList) {
  PassengerList q = cusLinkList;
  cusLinkList = (PassengerNode *)malloc(sizeof(PassengerNode));
  cusLinkList->next = NULL;
  return 0;
}

// 初始化带头结点的链队列
int init_waitlist_quene(WaitlistQueue &q) {
  WaitlistNode *p;
  p = (WaitlistNode *)malloc(sizeof(WaitlistNode));
  if (p == NULL) {
    printf("Error: out of memory\n");
    return 0;
  }
  p->next = NULL;
  q.front = q.rear = p; // 队空
  return 1;
}

// 通过起点站名和终点站名搜索对应航班
void search_flight_by_points() {
  char from[10];
  char to[10];
  int flag = 0;
  printf("请输入起点站名:");
  scanf("%s", from);
  printf("请输入终点站名:");
  scanf("%s", to);
  struct _Flight *p;
  p = pFlight->next;
  printf("起点  终点  编号  飞机号  飞行日期  总载客  余票量  1级余量  2级余量 "
         "\n");
  while (p != NULL) {
    if ((strcmp(from, p->departure) == 0) && (strcmp(to, p->destination) == 0))
    // 	对比输入的起点和终点，推荐航班
    {
      flag = 1;
      printf("%4s  %4s  %2s     %5s %8s  %5d   %5d  %6d     %4d\n",
             p->departure, p->destination, p->flight_id, p->plane_id, p->day,
             p->capacity, p->remaining_ticket_quantity,
             p->remaining_ticket_quantity1, p->remaining_ticket_quantity2);
    }
    p = p->next;
  }
  printf("\n\n");
  if (flag == 0)
    printf("不存在该航班！ \n");
}

// 订票函数
void book_ticket() {
  struct _Flight *info;
  int need, seat_level;
  int num; // 剩余的等级1数目或者等级2数目
  char name[20];
  char id[20];
  char day[20];
  // 输入想订的航班，看是否还有空位置，并返回复制节点
  info = search_flight_by_id();
  if (info == NULL) {
    printf("不存在该航班！\n");
    book_ticket();
  }
  printf("请输入您想要定的票数:");
  scanf("%d", &need);
  if (need <= 0) {
    printf("请输入您想要定的票数:");
    scanf("%d", &need);
  }
  printf("请输入您的票的舱位等级(1或2):");
  scanf("%d", &seat_level);
  switch (seat_level) {
  case 1:
    num = info->remaining_ticket_quantity1;
    break;
  case 2:
    num = info->remaining_ticket_quantity2;
    break;
  }
  // 订票数小于剩余数
  if (need <= num) {
    int i;
    printf("请输入您的姓名:");
    scanf("%s", name);
    printf("请输入您的身份证号码:");
    scanf("%s", id);
    printf("请输入你的飞行周期:");
    scanf("%s", day);
    PassengerList head = info->passenger_list;
    // 订票成功，插入成员名单链表
    add_passenger(head, need, name, id, day, seat_level);
    for (i = 0; i < need; i++)
      printf("%s 的座位号是: %d\n", name,
             info->capacity - info->remaining_ticket_quantity + i + 1);
    info->remaining_ticket_quantity -= need;
    switch (seat_level) {
    case 1:
      info->remaining_ticket_quantity1 -= need;
      break;
    case 2:
      info->remaining_ticket_quantity2 -= need;
      break;
    }
    printf("\n订票成功！\n");
  } else {
    char r;
    printf("该等级的票不足，以下为该航班乘客信息\n");
    print_flight_info(info); // 输出该航班的订票信息
    printf("是否改变订票计划?Y/N\n");
    r = getchar();
    printf("%c", r);
    if (r == 'Y' || r == 'y') // 改变计划，重新选择航班
    {
      book_ticket(); // 返回订票主页面
    } else {
      printf("\n您需要排队等候吗?(Y/N)");
      r = getchar();
      printf("%c", r);
      if (r == 'Y' || r == 'y') { // 不改变计划，排队候票
        printf("\n请输入您的姓名(排队订票):");
        scanf("%s", name);
        printf("\n请输入您的身份证(排队订票):");
        scanf("%s", id);
        if (seat_level == 1) // 进入1等舱排队队列
        {
          info->waitlist_1 = enqueue_waitlist(info->waitlist_1, name, need, id);
        } else // 进入2等舱排队队列
        {
          info->waitlist_2 = enqueue_waitlist(info->waitlist_2, name, need, id);
        }
        printf("\n排队成功!\n");
      }
    }
  }
}

// 根据自己输入的航班标号查询是否存在并返回节点
Flight *search_flight_by_id() {
  char number[10];
  int i = 0;
  printf("请输入航班编号: ");
  scanf("%s", number);
  Flight *p = pFlight->next; // 头结点的下一个节点开始遍历
  while (p != NULL) {
    if (!strcmp(number, p->flight_id))
      return p;
    p = p->next;
  }
  return NULL;
}

// 插入到已经订票客户链表
PassengerList add_passenger(PassengerList &head, int need, char name[],
                            char id[], char day[], int grade)

{
  PassengerList new1; // 创建一个新节点
  new1 = (PassengerNode *)malloc(sizeof(PassengerNode));
  if (new1 == NULL) {
    printf("\n内存不足\n");
    return NULL;
  }
  strcpy(new1->name, name);
  strcpy(new1->ID, id);
  strcpy(new1->day, day);
  new1->ticketCount = need;
  new1->seat_level = grade;
  new1->next = head->next; // 头插入法加入成员名单域
  head->next = new1;
  return head;
}

// 输出p节点的航班信息
void print_flight_info(Flight *p) {
  printf("起点  终点  编号  飞机号  飞行日期  总载客  余票量  1级余量  2级余量 "
         "\n");
  printf("%4s  %4s  %2s     %5s %8s  %5d   %5d  %6d     %4d\n", p->departure,
         p->destination, p->flight_id, p->plane_id, p->day, p->capacity,
         p->remaining_ticket_quantity, p->remaining_ticket_quantity1,
         p->remaining_ticket_quantity2);
  printf("\n\n");
}

// 入队，增加排队等候的客户名单域
WaitlistQueue enqueue_waitlist(WaitlistQueue &q, char name[], int need,
                               char id[])

{
  Waitlist new1;
  new1 = (Waitlist)malloc(sizeof(WaitlistNode));
  strcpy(new1->name, name);
  strcpy(new1->ID, id);
  new1->required_sticket_number = need;
  new1->next = NULL;
  q.rear->next = new1;
  q.rear = new1;
  return q;
}
PassengerInfo dequeue_waitlist1(FlightList &f) {
  PassengerInfo ret;
  WaitlistQueue q = f->waitlist_1;
  Waitlist free_require = q.front->next;
  q.front->next = q.front->next->next;
  strcpy(ret.ID, free_require->ID);
  strcpy(ret.name, free_require->name);
  strcpy(ret.day, f->day);
  ret.num = free_require->required_sticket_number;
  free(free_require);
  return ret;
}

PassengerInfo dequeue_waitlist2(FlightList &f) {
  PassengerInfo ret;
  WaitlistQueue q = f->waitlist_1;
  Waitlist free_require = q.front->next;
  q.front->next = q.front->next->next;
  strcpy(ret.ID, free_require->ID);
  strcpy(ret.name, free_require->name);
  strcpy(ret.day, f->day);
  ret.num = free_require->required_sticket_number;
  free(free_require);
  return ret;
}
// 退票功能
void cancel_ticket() {
  struct _Flight *info;
  int grade;
  PassengerNode *p1, *p2, *head; // p1为遍历指针，p2指向p1的前驱
  char name[20];                 // 客户姓名
  char id[20];                   // 客户身份证
  char day[20];
  info =
      search_flight_by_id(); // 复制节点信息给info，find函数根据航班编号返回该航班节点的指针
  while (info == NULL) {
    printf("没有这个航班, 请重新输入\n");
    cancel_ticket();
  }
  head = info->passenger_list; // head为该航班的的乘员名单域的头指针
  p1 = head->next; // 带头结点的指针，head->next 开始遍历
  printf("请输入你的姓名: ");
  scanf("%s", name);
  printf("请输入你的身份证号码: ");
  scanf("%s", id);
  printf("请输入飞行周期: ");
  scanf("%s", day);
  p2 = head;           // 根据客户姓名搜索客户是否订票
  while (p1 != NULL) { // 对比姓名和身份证
    if ((strcmp(name, p1->name) == 0) && (strcmp(id, p1->ID) == 0) &&
        (strcmp(day, p1->day) == 0))
      break;
    p2 = p1;
    p1 = p1->next;
  }
  if (p1 == NULL) {
    printf("对不起，你没有订过票或姓名和身份证,与飞行周期不对应\n");
    return;
  } else { // 退票成功
    // 从乘客名单域中移除该节点
    grade = p1->seat_level;
    p2->next = p1->next;
    // 加回该航班的剩余票
    info->remaining_ticket_quantity += p1->ticketCount;
    if (grade == 1) {
      info->remaining_ticket_quantity1 += p1->ticketCount;
    } else {
      info->remaining_ticket_quantity2 += p1->ticketCount;
    }
    printf("%s  成功退票！\n", p1->name);
    free(p1);
    //退票后确定是否有足够剩余使得waitlist转移至乘客
    Waitlist headnode1;
    headnode1 = info->waitlist_1.front->next;
    while (headnode1) {
      if (headnode1->required_sticket_number > info->remaining_ticket_quantity1)
        break;
      PassengerInfo unwait;
      unwait = dequeue_waitlist1(info);
      add_passenger(info->passenger_list, unwait.num, unwait.name, unwait.ID,
                    unwait.day, 1);
      info->remaining_ticket_quantity -= unwait.num;
      info->remaining_ticket_quantity1 -= unwait.num;
      headnode1 = info->waitlist_1.front->next;
    }
    Waitlist headnode2;
    headnode2 = info->waitlist_2.front->next;
    while (headnode2) {
      if (headnode2->required_sticket_number > info->remaining_ticket_quantity2)
        break;
      PassengerInfo unwait;
      unwait = dequeue_waitlist2(info);
      add_passenger(info->passenger_list, unwait.num, unwait.name, unwait.ID,
                    unwait.day, 2);
      info->remaining_ticket_quantity -= unwait.num;
      info->remaining_ticket_quantity2 -= unwait.num;
      headnode2 = info->waitlist_2.front->next;
    }
  }
}

// 插入删除节点的界面
void add_delete_flight_interface() {
  int a2;
  printf("\n");
  printf("\n");
  printf("\n");
  printf("\n");

  printf("                            插入与删除\n");
  printf("***********************************************************\n");
  printf("                            1.增加航班              \n");
  printf("                            2.删除航班              \n");
  printf("                            3.返回上一级            \n");
  printf("***********************************************************\n");
  printf("                            请输入你要办理的业务:");
  scanf("%d", &a2);
  switch (a2) {
  case 1:
    add_flight(); // 增加航班节点函数
    add_delete_flight_interface();
    break;
  case 2:
    if (1 == delete_flight()) // 删除航班节点函数
    {
      printf("删除成功\n");
    } else {
      printf("没有这个航班，删除失败！\n");
    };
    add_delete_flight_interface();
  case 3:
    show_menu();
    break;
  default:
    add_delete_flight_interface();
  }
}

// 增加航班函数
int add_flight() {
  FlightNode *q; // 定义q为新增加的航班结点的指针的形参
  Flight *p = pFlight;
  int y = 1;
  while (y != 0) {
    q = (FlightNode *)malloc(sizeof(FlightNode));
    if (q == NULL)
      return 0;
    printf("\t\t请依次输入以下内容\n");
    printf("\t\t请输入航班编号\n");
    scanf("%s", q->flight_id);
    int t = compare_flight_id(pFlight,
                              q->flight_id); // 判断添加的航班编号是否已经存在
    if (t == 0) {
      printf("该航班编号已经存在，请重新输入航班编号\n");
      continue;
    }
    printf("\t\t请输入起点站名\n");
    scanf("%s", q->departure);
    printf("\t\t请输入终点站名\n");
    scanf("%s", q->destination);
    printf("\t\t请输入飞机号\n");
    scanf("%s", q->plane_id);
    printf("\t\t请输入飞行日期\n");
    scanf("%s", q->day);
    printf("\t\t请输入乘客定额\n");
    scanf("%d", &q->capacity);
    q->remaining_ticket_quantity = q->capacity;
    printf("\t\t请输入1等票数目\n");
    scanf("%d", &q->remaining_ticket_quantity1);
    q->remaining_ticket_quantity2 =
        q->capacity - q->remaining_ticket_quantity1; // 1等票 = 总票数目 - 2等
    init_passenger_list(q->passenger_list);          // 初始化
    init_waitlist_quene(q->waitlist_1); // 将两种等级的票入队，方便等候计算
    init_waitlist_quene(q->waitlist_2);

    q->next = p->next;
    p->next = q;

    printf("\t\t是否继续录入航班信息(任意数字继续，0表示停止)。\n");
    printf("\t\t请输入:");
    scanf("%d", &y);
  }
  return 0;
}

// 删除航班函数
int delete_flight() {
  char ID[20];
  printf("请输入航班ID\n");
  scanf("%s", ID);
  FlightList pre = pFlight;
  FlightList p = pre->next;
  while (p != NULL) {
    if (!strcmp(ID, p->flight_id)) {
      pre->next = p->next;
      free(p);
      return 1;
    }
    pre = p;
    p = p->next;
  }
  return 0;
}

// 对比航班的编号，防止增加航班时，出现重复
int compare_flight_id(Flight *flight, char ID[]) {
  Flight *p = flight;
  while (p != NULL) {
    if (!strcmp(ID, p->flight_id)) {
      return 0; // 航班ID重复
    }
    p = p->next;
  }
  // ID不重复
  return 1;
}

// 搜索界面
void search_interface() {
  int a2;
  printf("\n");
  printf("\n");
  printf("\n");
  printf("\n");

  printf("                            搜索航班\n");
  printf("***********************************************************\n");
  printf("                            1.搜索航班            \n");
  printf("                            2.返回上一级          \n");
  printf("***********************************************************\n");
  printf("                            请输入您的选择:");
  scanf("%d", &a2);
  switch (a2) {
  case 1:
    search_flight_by_points(); // 输入起点和终点搜索航班

    search_interface();
    break;
  case 2:
    show_menu();
    break;
  default:
    search_interface();
  }
}

// 订票界面
void book_ticket_interface() {
  int a3;
  printf("\n");
  printf("\n");
  printf("                            订票\n");
  printf("***********************************************************\n");
  printf("                            1.订票                         \n");
  printf("                            2.由起点和终点搜索航班           \n");
  printf("                            3.搜索所有航班                     \n");
  printf("                            4.通过航班编号查询客户       \n");
  printf("                            5.返回上一级                  \n");
  printf("***********************************************************\n");
  printf("                            请输入你要办理的业务:");
  scanf("%d", &a3);
  switch (a3) {
  case 1: // 订票
    book_ticket();

    book_ticket_interface();
    break;
  case 2: // 输入起点和终点查询
    search_flight_by_points();

    book_ticket_interface();
    break;
  case 3:
    list_flights(pFlight);

    book_ticket_interface();
    break;
  case 4: // 查到客户的姓名和订票量
    print_passenger_info();

    book_ticket_interface();
    break;
  case 5:
    show_menu();
    break;
  default:
    book_ticket_interface();
  }
}

// 退票模块界面
void cancel_ticket_interface() {
  int a3;
  printf("\n");
  printf("\n");
  printf("                            退票\n");
  printf("***********************************************************\n");
  printf("                            1.办理退票            \n");
  printf("                            2.返回上一级          \n");
  printf("***********************************************************\n");
  printf("                            请输入你要办理的业务:");
  scanf("%d", &a3);

  switch (a3) {
  case 1:
    cancel_ticket();

    cancel_ticket_interface();
    break;
  case 2:
    show_menu();
    break;
  default:
    cancel_ticket_interface();
  }
}

// 输出订购该航班乘客的姓名，票数，等级
void print_passenger_info() {
  PassengerList p;
  Flight *info;
  info =
      search_flight_by_id(); // 由输入的航班编号查询航班是否存在，并将节点复制给info
  if (info == NULL) {
    printf("没有这个航班\n");
    return;
  }
  // 头结点的下一个节点开始遍历
  p = info->passenger_list->next;
  if (p != NULL) {
    printf("客户姓名   订票数额   舱位等级(1经济舱，2商务舱)\n");
    while (p) {
      printf("%s\t\t%d\t%d\n", p->name, p->ticketCount, p->seat_level);
      p = p->next;
    }
  } else
    printf("该航班没有客户信息!!\n");
}

// 打印全部航班信息
void list_flights(Flight *pflight) {
  Flight *p;
  p = pflight->next;
  printf("起点  终点  编号  飞机号  飞行日期  总载客  余票量  1级余量  2级余量 "
         "\n");
  while (p != NULL) {
    printf("%4s  %4s  %2s     %5s %8s  %5d   %5d  %6d     %4d\n", p->departure,
           p->destination, p->flight_id, p->plane_id, p->day, p->capacity,
           p->remaining_ticket_quantity, p->remaining_ticket_quantity1,
           p->remaining_ticket_quantity2);
    p = p->next;
  }
  printf("\n\n");
}

// 菜单界面函数
int show_menu() {
  int i;
  do {
    {
      // system("color 9e");
      printf("\n");
      printf("\n");
      printf("                            航空订票系统\n");
      printf("***********************************************************\n");
      printf("                            1.  航班列表             \n");
      printf("                            2.  搜索航班             \n");
      printf("                            3.  订票                 \n");
      printf("                            4.  退票                 \n");
      printf("                            5.  录入与删除           \n");
      printf("                            6.  退出                \n");
      printf("***********************************************************\n");
      printf("                           输入需要办理的业务:");
      scanf("%d", &i);
    }
    switch (i) {
    case 1:
      list_flights(pFlight); // 打印全部航班信息

      show_menu();
      break;
    case 2:
      search_interface(); // 搜索界面

      show_menu();
      break;
    case 3:
      book_ticket_interface(); // 订票界面

      show_menu();
      break;
    case 4:
      cancel_ticket_interface(); // 退票界面

      show_menu();
      break;
    case 5:
      add_delete_flight_interface(); // 插入和删除新节点

      show_menu();
      break;
    case 6:
      exit(0);
    default:
      show_menu(); // 返回主菜单
    }
  } while (0);
  return 0;
}

int main() {
  init_flights();                 // 初始化航班链表
  init_add_flight(InitialFlight); // 将航标信息插入链表
  show_menu();                    // 菜单
  return 0;
}
